package Exams.FeiBu;

import java.util.*;

public class q3 {
    // 会员题 582
    // BFS的方式解决
    public List<Integer> bfs_killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < ppid.size(); i++) {
            if (ppid.get(i) > 0) {
                List<Integer> l = map.getOrDefault(ppid.get(i), new ArrayList<Integer>());
                l.add(pid.get(i));
                map.put(ppid.get(i), l);
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> l = new ArrayList<>();
        queue.add(kill);
        while (!queue.isEmpty()) {
            int r = queue.remove();
            l.add(r);
            if (map.containsKey(r))
                for (int id : map.get(r))
                    queue.add(id);
        }
        return l;
    }

    // DFS的方式解决
    public List<Integer> dfs_killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < ppid.size(); i++) {
            if (ppid.get(i) > 0) {
                List<Integer> l = map.getOrDefault(ppid.get(i), new ArrayList<Integer>());
                l.add(pid.get(i));
                map.put(ppid.get(i), l);
            }
        }
        List<Integer> l = new ArrayList<>();
        l.add(kill);
        getAllChildren(map, l, kill);
        return l;
    }

    public void getAllChildren(HashMap<Integer, List<Integer>> map, List<Integer> l, int kill) {
        if (map.containsKey(kill))
            for (int id : map.get(kill)) {
                l.add(id);
                getAllChildren(map, l, id);
            }
    }
}

